// ARBB.h: interface for the ARBB class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ARBB_H__2FA32400_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_)
#define AFX_ARBB_H__2FA32400_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "Type.h"
#include "UserARBB.h"

class NodARBB;

/*
	Clasa ARBB implementeaza tipul arborelui B, definit ca un arbore perfect
	echilibrat ce satisface urmatoarele conditii:

	1) n este odinul arborelui;
	2) nodurile sale sunt pagini; paginile contin cel mult 2*n chei; numarul de
		chei dintr-o pagina este dimensiunea paginii;
	3) orice pagina, cu exceptia radacinii are un numarul de chei minim n, iar
		radacina minim 1;
	4) orice pagina de dimensiune m, cu exceptia celor terminale, are exact
		m+1 descendenti;
	5) paginile terminale sunt pe acelasi nivel.

	ARBB este mai mult o interfata intre aplicatie si clasa Pagina.
	Pentru creare trebuie specificat ordinul arborelui si tipul lui.
	Odata acestea stabilite, ele nu mai pot fi schimbate.
	Exista 2 moduri de creare:
		- prin constructorul specific
		- prin constructoru implicit si apoi apeland functia SettleToBe
	
	Este derivata din UserARBB, deoarece se foloseste pe ea insasi sa
	localizeze un nod!
*/

class ARBBDLL_API ARBB : virtual public UserARBB {

protected:

	unsigned
		// ordinul arborelui
		n,
		// numarul curent de noduri
		N,
		// numarul curent de pagini
		P,
		// numarul curent de nivele
		L;
	
	// unicul obiect Pagina
	class Pagina* p;

	// Lista dublu inlantuita cu cate un nod per nivel.
	typedef	struct tagLevList {
		unsigned
			// primele 3 sunt folosit la plimbarea efectiva prin arbore
			// numarul nivelului
			nLev,
			// indice in pagina parinte
			nInd,
			// dimensiunea paginii parinte;
			nSize,
			// pentru subarbore mai folosesc
			// numarul de pagini de pe acest nivel
			nPag,
			// numarul de noduri de pe acest nivel
			nNod;
	
		TImplPag
			// pagina parinte ( NULL pentru radacina )
			par;

		struct tagLevList
			// urmatorul nivel
			* urm,
			// anteriorul nivel
			* ant;
	} TLevNod;
	
	TLevNod
		* pLevCap, // capul listei
		* pLevCoada, // coada listei
		* pLev; // pe acest nivel interoghez paginile
	
	BOOL
		// arborele e implicat in desenarea unui subarbore
		bSnake,
		// arborele e implicat in determinarea unui subarbore
		bGrep,
		// se va traversa un subarbore, nu intreg arborele
		bSubTree;
	
	/* exista 3 cazuri posibile: OnEachNode, OnEachPage
	*/
	struct {
		union {
			// pointer la o functie
			void* pFnc;
			// sau pointer la un obiect
			UserARBB* pUser;
		} u;
		// apel de tip this sau nonthis
		BOOL bType;
	} aCC[ 2 ];

	// Pointer la structura de comunicare.
	TPageInfo* pPI;

	// Pentru GrepSubTree sau WalkOnSnake sau Draw.
	UserARBB* pUser;

	// La localizare trebuie sa stiu pe cine caut.
	const NodARBB* pLoc;

	// Semafor pentru desenare.
	static BOOL bSemDraw;

	/* Este de tipul argumentului primit de functia GrepSubTree. Determina cate
		nivele pot desena.
	*/
	static BOOL testdraw ( unsigned nLevels, unsigned nNodes, unsigned nPages );

	// Extra membrii statici pentru desenare:
	// variabile folosite de functia de mai sus
	static unsigned vl;
	// inaltimea, latimea dreptunghiului ce incadreaza un nod 
	// distanta dintre doua noduri vecine in aceeasi pagina
	static unsigned dl;
	// hnod = hl + dl
	static unsigned hnod;
	// distanta dintre nivele, pagini
	static unsigned hgap;
	static unsigned vgap;
	// dimensiunea maxima a desenului pe orizontala, verticala
	static unsigned maxh;
	static unsigned maxv;
	// numarul maxim de nivele
	static unsigned maxlev;
	/* unde am ajuns pe verticala, orizontala
		la sfarsitul PreDraw reprezinta dimensiunile dreptunghiului
		ce incadreaza desenul subarborelui.
	*/
	static unsigned vsize;
	static unsigned hsize;
	
	// Apelate din clasa Pagina pentru a apela mai departe ce s-a dorit
	void travpage ( BOOL bCall );
	void travnode ( const NodARBB* pNod );

	// setare din interior a *pPI
	void mapcombuff ( unsigned nLevel, unsigned nBros, unsigned nCount, unsigned nDim ) const;

	// Gestionarea listei
	// Eliberare lista de nivele
	void freelist ();
	
	// Cand creste inaltimea arborelui, apare pagina p.
	void incheight ( TImplPag p );

	// Cand scade inaltimea arborelui
	void decheight ();

	// Foloseste la copy-constructor
	void initlist ( TImplPag p );

	// Trec la pagina frate din stanga, dreapta
	BOOL leftpage ();
	BOOL rightpage ();

	// cateva initializari la constructie
	void init ();

	// urmatoarele variabile membru tin de traversarea arborelui
	BOOL 
		// tipul arborelui: vezi constructorul
		t,
		// arborele e implicat in traversare pe noduri
		bNode,
		// arborele e implicat in traversare pe pagini
		bPage,
		// s-a setat tipul arborelui ?
		bSet,
		// se pot bloca inserarile si suprimarile
		bLock, bLockShadow, bLockPrev;

public:

	// Constructor implicit
	ARBB ();
	
	/* Setare tip arbore ( vezi mai jos ). Returneaza FALSE daca arborele a
		fost creat deja cu un anume tip. Altfel TRUE.
	*/
	BOOL SettleToBe ( unsigned nDimPagina, BOOL bTipPagina );

	/* Constructor
		Argumente:
		  nDimPagina -> dimensiunea paginii = ordinul arborelui
		  bTipPagina -> tipul paginii -> TRUE  -> cu pointeri
													 FALSE -> cu cursori
	*/
	ARBB ( unsigned nDimPagina, BOOL bTipPagina );
	
	// Copy constructor
	ARBB ( const ARBB& );

	// Operator de copiere
	ARBB& operator =( const ARBB& );

	// Destructor
	~ARBB();

	// Tipul implementarii
	BOOL Type () const;
	
	// Ordinul arborelui
	unsigned Ord () const;

	// Numarul de noduri din arbore
	unsigned Card () const;
	unsigned NoNodes () const;

	// Numarul de pagini din arbore
	unsigned NoPages () const;

	// Numarul de nivele din arbore
	unsigned NoLevels () const;

	/* Operatori de inserare, suprimare si cautare
		Argumentul "pNod" este un pointer la un obiect NodARBB
	*/
	BOOL operator +=( NodARBB* pNod );
	BOOL Insert ( NodARBB* pNod );

	BOOL operator -=( NodARBB* pNod );
	BOOL Extract ( NodARBB* pNod );

	BOOL operator []( NodARBB* pNod ) const;
	BOOL Search ( NodARBB* pNod ) const;

	/* Operatori de inserare, suprimare si cautare
		Argumentul "rNod" este o referinta la un obiect NodARBB
	*/
	BOOL operator +=( NodARBB& rNod );
	BOOL Insert ( NodARBB& rNod );

	BOOL operator -=( NodARBB& rNod );
	BOOL Extract ( NodARBB& rNod );

	BOOL operator []( NodARBB& rNod ) const;
	BOOL Search ( NodARBB& rNod ) const;

	// Functii de interogare arbore vid
	BOOL IsVoid () const;
	BOOL operator !() const;

	// Operatori de vidare arbore
	BOOL Void ();
	BOOL operator ~();

	// Functii de interogare maxim si minim
	const NodARBB* Max () const;
	const NodARBB* operator +() const;
	const NodARBB* Min () const;
	const NodARBB* operator -() const;

	// Blocare / deblocare / interogare blocare inserari si suprimari
	BOOL Lock ();
	BOOL Unlock ();
	BOOL IsLocked () const;

	// Rata gasirii nodurilor in nodul sau pagina cache la cautare.
	double CacheHitRate () const;

	// Returneaza, in procente, gradul de utilizare a memoriei.
	double MemUsage () const;

	// Depune istoria operatiilor la adresa pointata de pDst.
	BOOL GetStatus ( TStatus* pDst ) const;

	// Impune o istorie a operatiilor prin structura pointata de argument.
	BOOL SetStatus ( const TStatus* pSrc );

	/* O serie de functii de traversare apeleaza o functie sau metoda
		( callback ), deci e necesar un tampon de comunicare intre cele 3
		functii: functia aplicatie apelanta, de traversare si callback; el
		trebuie setat dinainte si i se poate interoga locatia totodata.
		Stabilirea acestui tampon se face inaintea fiecarui apel la o metoda
		ce foloseste acest tampon, deoarece acestea sterg pointerul la tampon
		la sfarsitul executiei lor.
	*/
	void SetComBuff ( TPageInfo& rPI );
	const TPageInfo* GetComBuff () const;
	
	/* Metode de traversare: pe pagini sau pe noduri

		Functiile PREgatire TRAVersare returneaza:
		 TRUE -> se poate incepe traversarea prin apelarea OnEachxxxx (...)
		 FALSE -> arborele este deja implicat intr-o operatie de traversare

		Procedurile OnEachxxxx ( ... ) returneaza:
		  TRUE -> arborele s-a traversat
		  FALSE -> arborele este deja implicat intr-o traversare

		Cele doua traversari nu interfera intre ele.
		Argumentul bType specifica tipul primului argument
	*/
	BOOL PreNodeTrav () const;
	/* Pentru fiecare nod, in inordine, se apeleaza o functie; 
		Primul prototip seteaza pe pUser si apeleaza pe al doilea cu pDep=NULL,
		putand astfel distinge intre cele 2 tipuri de apeluri dorite.
	*/
	BOOL OnEachNode ( UserARBB& rUsr );
	BOOL OnEachNode ( void* pDep );

	BOOL PrePageTrav () const;
	/* Procedura OnEachPage primeste ca argumente:
		 tOrder -> specifica ordinea de traversare:
			-1 -> preordine, adica mai intai pagina curenta,
			      apoi subpaginile referite de ea ( implicit )
			+1 -> postordine, adica invers fata de cum e mai sus
			 0 -> se parcurge pagina curenta de 2 ori, intre cele 2 se parcurg
				  subarborii descendenti.
		Primul prototip seteaza pe pUser si apeleaza pe al doilea cu pDep=NULL,
		putand astfel distinge intre cele 2 tipuri de apeluri dorite.
	*/
	BOOL OnEachPage ( UserARBB& rUsr, int tOrder = -1 );
	BOOL OnEachPage ( void* pDep, int tOrder = -1 );

	/* Operatorul de indexare returneaza un pointer la un nod din pagina curenta si de indice
		egal cu cel primit ca argument:
	 nIndice -> valoare intre 1 si nCount.
		Daca arborele nu e implicat intr-o travesare, returneaza NULL.
		Este utilizat fie la desenare, fie la traversare pe pagini, fie la
		traversare pe nivele.
	*/
	const NodARBB* operator []( unsigned nIndice ) const;

	/* Trebuie apelata NEAPARAT cand se insereaza primul nod in arbore sau
		daca se doreste reinitializarea traversarii la radacina.
	*/
	BOOL RootLevel ();

	// Se salveaza pagina curenta, un nivel mai sus, se incarca pagina memorata
	BOOL PrevLevel ();

	// Analog, cu un nivel mai jos
	BOOL NextLevel ();

	// Spre stanga cu o pagina, pe acelasi nivel
	BOOL PrevPage ();

	// Spre dreapta cu o pagina, pe acelasi nivel
	BOOL NextPage ();

	// Nivelul curent
	unsigned CrtLevel () const;

	// Pot sa incerc sa cuprind un subarbore ?
	BOOL PreGrep () const;

	/* Incearca sa "cuprinda" o parte din subarborele curent; se poate traversa
		apoi apeland OnEachPage ( RECURSIV ) sau WalkOnSnake ( ITERATIV ).
		Returneaza 0 daca nu a putut cuprinde un subarbore, altfel numarul de
		nivele cuprinse. In caz de insucces si daca a existat inainte un alt
		subarbore cuprins, se revine la el.
		Primul prototip seteaza pe pUser si apeleaza pe al doilea cu pDep=NULL,
		putand astfel distinge intre cele 2 tipuri de apeluri dorite.
	*/
	unsigned GrepSubTree ( UserARBB& rUsr );
	unsigned GrepSubTree ( void* pDep );

	/* Dupa ce s-a "cuprins" un subarbore sau s-a apelat RootLevel(), el se
		poate parcurge pe nivele, intr-o maniera serpuita, adica dreapta, jos,
		stanga, jos samd. Se poate OPRI	"serpuirea" prin functia care se
		apeleaza pentru fiecare pagina ( daca returneaza TRUE ); aici se poate
		accesa un nod din pagina cu operatorul de indexare []. Ambele functii
		returneaza FALSE daca nu se poate incepe serpuirea; a doua functie mai
		returneaza FALSE si daca serpuirea s-a terminat de la sine, caz in care
		pagina curenta ( care este radacina (sub)arborelui ) redevine cea care a
		fost, altfel, daca functia aplicatie a returnat	TRUE, returneaza TRUE
		si seteaza pagina radacina. Pagina radacina este in acelasi (sub)arbore
		(cel cuprins inainte); sub(sub)arborele a carui radacina este devine
		subarborele curent.
		Primul prototip seteaza pe pUser si apeleaza pe al doilea cu pDep=NULL,
		putand astfel distinge intre cele 2 tipuri de apeluri dorite.
	*/
	BOOL PreWalk () const;
	BOOL WalkOnSnake ( UserARBB& rUsr );
	BOOL WalkOnSnake ( void* pDep );

	/* Aplicatie la WalkOnSnake: se localizeaza nivelul si pagina ce contin
		nodul pNod.
	*/
	// Singura metoda din UserARBB ce o folosesc, este pentru localizare.
	BOOL OnWalkARBB ();
	BOOL Locate ( const NodARBB* pNod );

	/* Ce urmeaza este o aplicatie incorporata a metodei de cuprindere
		de subarbore, anume desenarea unui subarbore pe un plan.
		Desenarea incepe de la cel mai de jos nivel, alocand uniform spatiul
		pentru o pagina, pe fiecare nivel.
	*/

	/* Returneaza 0 daca momentan nu se poate desena subarborele; subarborele
		nu se poate desena daca arborele e implicat in traversarea pe PAGINI
		sau deja e in desenare. Altfel returneaza numarul de nivele care se pot
		desena, respectand conditiile impuse. Deoarece amaxh si amaxv sunt
		referinte, la revenire in ele voi avea dimensiunile dreptunghiului ce 
		incadreaza desenul (sub)arborelui.
		Argumentele se mapeaza pe membrii statici de mai sus.
		amaxlev = 0 inseamna pe maximul de nivele posibil.
		```````````
	*/
	unsigned PreDraw (
					unsigned ahl, unsigned avl,
					unsigned ahgap, unsigned avgap,
					unsigned& amaxh, unsigned& amaxv,
					unsigned amaxlev = 0, unsigned adl = 1
					);
	
	/* Se apeleaza dupa ce in prealabil s-a apelat PreDraw.
		Primul prototip seteaza pe pUser si apeleaza pe al doilea cu pDep=NULL,
		putand astfel distinge intre cele 2 tipuri de apeluri dorite.
	*/
	BOOL Draw ( UserARBB& rUsr );
	BOOL Draw ( void* pDep );

	friend class PaginaCrs;
	friend class PaginaPtr;

};

/*
Nota:
	Nu pot folosi simultan:
		Draw cu GrepSubTree;
		Draw cu Locate sau cu WalkOnSnake;
		WalkOnSnake cu Locate.
	Simultan inseamna ca apelez o metoda intr-o functie callback, metoda care
	nu are voie sa se suprapuna cu metoda deja apelata.
*/

#endif // !defined(AFX_ARBB_H__2FA32400_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_)
